from queue import Queue


class TreeNode(object):
    """Class description."""

    def __init__(self, val: int) -> None:
        super().__init__()
        self.val = val
        self.left = None
        self.right = None


def level_order(root: TreeNode):
    """
    层序遍历

    :param root: 根节点
    :type root: TreeNode
    """
    queue = Queue()
    queue.put(root)
    while queue.qsize() > 0:
        root = queue.get()
        print(root.val, end=" ")
        if root.left is not None:
            queue.put(root.left)
        if root.right is not None:
            queue.put(root.right)
    print()


def pre_order(root: TreeNode):
    if root is None:
        return
    print(root.val, end=" ")
    pre_order(root.left)
    pre_order(root.right)


def in_order(root: TreeNode):
    if root is None:
        return
    in_order(root.left)
    print(root.val, end=" ")
    in_order(root.right)


def post_order(root: TreeNode):
    if root is None:
        return
    post_order(root.left)
    post_order(root.right)
    print(root.val, end=" ")


def main() -> None:
    # 初始化二叉树
    # 初始化节点
    n1 = TreeNode(val=1)
    n2 = TreeNode(val=2)
    n3 = TreeNode(val=3)
    n4 = TreeNode(val=4)
    n5 = TreeNode(val=5)
    # 构建节点之间的引用（指针）
    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5
    level_order(n1)
    pre_order(n1)
    print()
    in_order(n1)
    print()
    post_order(n1)
    print()


if __name__ == "__main__":
    main()
